package com.erbao.datastructurearithmetic.tyro;

import com.erbao.datastructurearithmetic.RandomUtil;

/**
 * @author CaoBaoYin
 * @since 21/8/11 16:34
 */
public class Class8 {

    public static void main(String[] args) {
        // System.out.println(3/2);
        /*int maxValue = 100;
        int maxLen = 100;
        int testTimes = 1000000;
        for (int i = 0; i < testTimes; i++) {
            int[] array = Class2.lenRandomAndValueRandom(maxLen, maxValue);
            mergeSortV2(array);
            if (!Class1.isSort(array)) {
                Class1.show(array);
                System.out.println("bad");
                break;
            }
        }
        System.out.println("nice");*/

        int[] array = RandomUtil.lenRandomAndValueRandom(30, 10);
        // int[] array = {1, 8, 3, 8, 3, 0, 3, 5, 8, 6, 6, 0, 7, 2, 7, 6, 3};
        Class1.show(array);
        System.out.println();
        partitionLRV2(array);
        Class1.show(array);
    }

    private static void partitionLR(int[] array){
        if (array==null || array.length<2) return;

        int length = array.length;
        int standard = array[length-1];
        int l = 0;
        int r = length-1;
        while ( l < r) {
            if (array[l] > standard) {
                Class1.swap(array, l, r--);
            } else {
                l ++;
            }

            if (array[r] <= standard) {
                Class1.swap(array, l++, r);
            } else {
                r --;
            }
        }
    }

    private static void partitionLRV2(int[] array) {
        if (array==null || array.length<2) return;

        int length = array.length;
        int leftCursor = -1;
        int standard = array[length-1];
        for (int i = 0; i < length; i++) {
            if (array[i] <= standard) {
                Class1.swap(array, ++leftCursor, i);
            }
        }
    }

    private static void partitionLER(int[] array, int left, int right) {
        if (left >= right) return;

        int standard = array[right];

    }

    /**
     * 左老师写法
     * @param arr
     */
    public static void mergeSortV3(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        int step = 1;
        int N = arr.length;
        while (step < N) {
            int L = 0;
            while (L < N) {
                int M = 0;
                if (N - L >= step) { // 够一组
                    M = L + step - 1;
                } else {// 不够一组
                    M = N - 1;
                }
                if (M == N - 1) {// 不够一组，不用合并
                    break;
                }
                int R = 0;
                if (N - 1 - M >= step) {// 右半部分够一组
                    R = M + step;
                } else {// 有半部分不够一组
                    R = N - 1;
                }
                merge(arr, L, M, R);
                if (R == N - 1) {// 刚好偶数组，无多余元素
                    break;
                } else {
                    L = R + 1;
                }
            }
            if (step > N / 2) {
                break;
            }
            step *= 2;
        }

    }

    /**
     * 归并排序（非递归）
     * @param array 待排序数组
     */
    private static void mergeSortV2(int[] array){
        if (array==null || array.length<2) {
            return;
        }

        int length = array.length;
        int groupSize = 1;// 分组大小
        /*分组大小大于或等于就不用排序合并了*/
        while (groupSize < length) {
            int groupNum = length/groupSize;// 判断可以分多少组。需要注意可能后面还有不够一组的部分
            boolean moreGroup = length % groupSize > 0;// 是否还有不够一组的
            int l = 0;
            for (int i = 0; i < groupNum; i+=2) {// 两组合并， i+2
                int mid = l + groupSize - 1, r = mid + groupSize;// 左右边界
                if (r > length-1) {// 此时只剩下最后一组，因为要两两合并，需要判断有没有下一组
                    if (! moreGroup) { // 没有下一组，只剩一组，无需合并，没用操作，直接跳出
                        break;
                    } else {// 还有一部分，但不够一组了
                        r = length-1;
                    }
                }
                merge(array, l, mid, r);
                l = r + 1;
            }// 循环结束可能还有不够一组的一部分，但是不用操作

            /*为防止groupSize溢出，需要做个判断*/
            if (groupSize > (length >> 1)) {
                break;
            } else {
                groupSize <<= 1;
            }
        }
    }

    /**
     * 归并排序（递归）
     * @param array 待排序数组
     */
    private static void mergeSort(int[] array) {
        if (array==null || array.length<2) {
            return;
        }

        mergeSort(array, 0 , array.length-1);
    }

    /**
     * 根据边界归并排序边界内部分
     * @param array 待排序数组
     * @param l 左边界（含）
     * @param r 右边界（含）
     */
    private static void mergeSort(int[] array, int l, int r) {
        if (l >= r) return;

        // 中间位置不用 l+r/2 的原因是数组很大时，l+r会溢出
        int mid = l + ((r-l) >> 1);
        // 左部分排序
        mergeSort(array, l, mid);
        // 右部分排序
        mergeSort(array, mid+1, r);
        // 两个部分排序后的结果进行合并
        merge(array, l, mid, r);
    }

    /**
     * 两个排序好的部分进行合并成一个有序部分
     * @param array 数组
     * @param l 左边界（含）
     * @param mid 中间位置角标
     * @param r 右边界（含）
     */
    private static void merge(int[] array, int l, int mid, int r) {
        int[] help = new int[r-l+1];
        int index = 0;
        int leftCursor = l;
        int rightCursor = mid+1;
        /*游标在两部分都未越界*/
        while (leftCursor <= mid && rightCursor<=r) {
            if (array[leftCursor] < array[rightCursor]) {
                help[index++] = array[leftCursor++];
            } else if (array[leftCursor] > array[rightCursor]) {
                help[index++] = array[rightCursor++];
            } else {
                help[index++] = array[leftCursor++];
                help[index++] = array[rightCursor++];
            }
        }

        /*右部分越界，左部分剩余的值直接拿过来*/
        while (leftCursor <= mid) {
            help[index++] = array[leftCursor++];
        }

        /*左部分越界，右部分剩余的直接拿过来*/
        while (rightCursor <= r) {
            help[index++] = array[rightCursor++];
        }

        /*辅助数组替换原有数组*/
        index=0;
        while (l <= r) {
            array[l++] = help[index++];
        }
    }
}
